/**53. 最大子数组和 
 * - 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 
 * - 子数组 是数组中的一个连续部分。
 */
export function maxSubArray(nums: number[] = [-2, 1, -3, 4, -1, 2, 1, -5, 4]): number {
    /**dp[i]：包括下标i（以nums[i]为结尾）的数组 的最大连续子序列和为dp[i]。 */
    const dp = nums.map((k) => k)//初始化为自身，因为自身也算是子数组
    let res = dp[0]
    for (let i = 1; i < nums.length; i++) {
        dp[i] = Math.max(dp[i], dp[i - 1] + nums[i])
        //                 重新计算    加上当前      
        if (res < dp[i]) res = dp[i]
    }
    // return Math.max(...dp)
    return res //优化：免得再去求dp最大值 
    return res
}

/** 300. 最长递增子序列 
 * - 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 * - 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 */
export function lengthOfLIS(nums: number[] = [1, 3, 6, 7, 9, 4, 10, 5, 6]): number {
    /**dp[i]表示 i之前(包括i)的 以nums[i]结尾的 最长递增子序列的长度 
     * - dp[i] = max(dp[i], dp[j] + 1)
     * - 位置i的最长递增子序列 等于 j: 0->i-1 各个位置的最长升序子序列 + 1 的最大值。
     */
    const dp = new Array(nums.length).fill(1) //填充1，因为最短也是1
    /**取长的子序列 */
    let result = 0;
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < i; j++) { //判断从0到i，谁最大
            //注意需要 nums[i] > nums[j] ，不然不是递增
            if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1)//发现有递增情况，如果以这个作为递增，是否比当前大，是的话就更新 
        }
        if (dp[i] > result) result = dp[i]; // 取长的子序列
    }

    return result
}
// 概括来说：不连续递增子序列的跟前0-i 个状态有关，连续递增的子序列只跟前一个状态有关 
/** 674. 最长连续递增序列 
 * - 给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
 * - exp: nums = [1,3,5,4,7] , 最长连续递增序列是 [1,3,5], 长度为3
 */
export function findLengthOfLCIS(nums: number[] = [1, 3, 5, 4, 7]): number {

    /**  dp[i]：以下标i为结尾的 连续递增的子序列 长度为dp[i]。*/
    const dp = new Array(nums.length).fill(1)
    /**最终结果 */
    let res = 0
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) {//如果是递增才
            dp[i] = dp[i - 1] + 1 //是上一个+1 （因为要求连续）
        }
        if (dp[i] > res) res = dp[i] //更新最大值
    }
    return res
}

/** 718. 最长重复子数组
 *  - 给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
 *  - 示例
 *  - 输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
    - 输出：3
    - 解释：长度最长的公共子数组是 [3,2,1] 。
 */
export function findLength(nums1: number[] = [1, 2, 3, 2, 1], nums2: number[] = [3, 2, 1, 4, 7]): number {
    /**  https://programmercarl.com/0718.最长重复子数组.html#思路
     * - dp[i][j] ：以下标i-1为结尾的数组A，和以下标j-1为结尾的数组B，最长重复子数组长度为dp[i][j]。 
     * - （特别注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 ）
     * - 根据dp定义，可以知道递推公式为 dp[i][j] = dp[i-1][j-1] + 1
     */
    const dp = Array.from({ length: nums1.length + 1 }, () => new Array<number>(nums2.length + 1).fill(0))
    let res = 0
    for (let i = 1; i <= nums1.length; i++) {
        for (let j = 1; j <= nums2.length; j++) {
            //数值相等时才可以赋值 （因为这题要求相同子序列）
            if (nums1[i - 1] == nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                res = Math.max(res, dp[i][j]) //取最大值 
            }
        }
    }
    return res
}

/**1143. 最长公共子序列   https://programmercarl.com/1143.最长公共子序列.html#算法公开课
 * - 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
 * - 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 
 */
export function longestCommonSubsequence(text1: string = "abcde", text2: string = "ace"): number {
    const length1 = text1.length
    const length2 = text2.length
    /**- dp[i][j]：长度为[0, i-1]的字符串text1，与长度为[0, j-1]的字符串text2，的最长公共子序列为dp[i][j]
     * - 如果text1[i-1] 与 text2[j-1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;
     * - 如果不相同，往前找最大的一个 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
     */
    const dp = Array.from({ length: length1 + 1 }, () => new Array(length2 + 1).fill(0))
    for (let i = 1; i <= length1; i++) {
        for (let j = 1; j <= length2; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

    }
    return dp[length1][length2]
}